package com.lcq.study.leetcode.cjsf;

/**
 * @ClassName 初级算法第1章07题
 * @Description
 * @Author lichuanqi
 * @Date 2022/10/27 17:45
 * @Version 1.0
 **/
public class cjsf108 {
    public static void main(String[] args) {
        cjsf108 solution = new cjsf108();
        int[] ints = {0,1,0,3,6,0,2,5,12,0, 19, 10, 9};
        solution.moveZeroes(ints);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }

    public void moveZeroes(int[] nums) {
        int length = nums.length;
        int i = 0;
        int j = length - 1;
        int tmp;
        while (i < j){
            if (nums[i] == 0 && nums[j] != 0){
                tmp = nums[j];
                nums[j] = nums[i];
                nums[i] = tmp;
            }

            if (nums[i] != 0){
                i++;
            }

            if (nums[j] == 0){
                j--;
            }
        }



        if (nums[j] != 0){
            sort(nums, 0, j);
        }else {
            sort(nums, 0, j-1);
        }

    }


    public void sort(int[] nums, int start, int end){
        if (end - start < 1){
            return;
        }

        int index = (end+start)/2;
        int v = nums[index];

        swap(nums, start, index);
        int i = start + 1;
        int j = end;
        while(i < j){
            if (nums[i] >= v && nums[j]< j){
                swap(nums, i, j);
            }

            if (nums[i] < v){
                i++;
            }

            if (nums[j] >= v){
                j--;
            }
        }


        if (nums[i] < nums[start]){
            index = i;
            swap(nums, start, i);
        }else {
            index = i - 1;
            swap(nums, start, i - 1);
        }


        sort(nums, start, index - 1);
        sort(nums, index+1, end);
    }

    public void swap(int[] nums, int a1, int a2){
        int tmp = nums[a1];
        nums[a1] = nums[a2];
        nums[a2] = tmp;
    }


}
